package com.hdu.other.dp.maxIncLen;

public class lc300 {
    class Solution {
        public int lengthOfLIS(int[] nums) {

            int n = nums.length;
            int len = 0;
            int[] ends = new int[n];

            for (int num : nums)
            {
                int find = find(ends, len, num);
                ends[find == -1 ? len++ : find] = num;
            }
            return len;
        }

        int find(int[] ends, int len, int target)
        {
            int l = 0, r = len - 1, ans = -1;
            while (l <= r)
            {
                int mid = l + ((r - l) >> 1);
                if (ends[mid] >= target)
                {
                    ans = mid;
                    r = mid - 1;
                }
                else
                {
                    l = mid + 1;
                }
            }
            return ans;
        }
    }
}
